1. Field of the Invention
The present invention relates generally to the prevention of computer memory misuse, and more specifically to such prevention utilizing cosets generated from a linear code.
2. Description of the Prior Art
Computer designers have sought to append "tag" information for data protection in the randomly accessed main memory of electronic digital computers. Such tags consist of one or more bits of information appended to to each word of memory to identify its legal classes of usage and thus prevent misuse. However, this tagging mechanism has rarely been employed in a commercially successful computer due to the cost of providing extra bits of storage. For example, each tag bit in a 32-data-bit machine requires 3% additional storage. Since main memory is a significant aspect of the cost of a computer system, appending such tags can be economically prohibitive.
A majority of commercial computers utilize "keys" to safeguard memory (See, Introduction to Computer Architecture, Stone et al, Science Research Associates, Inc., Chicago, 2nd edition, 1980, p. 607). With this technique, each block of memory is equipped with a tag of typically 4 to 8 bits, and each user is provided with a key of the same dimension. The user's key must match the tag in order to read or write into a designated memory area. While extensively employed, this technique is wanting owing to coarse granularity, that is, the block of data associated with each tag is large, often a thousand words. The size of the blocks is dictated by the cost of storing the tags; storing the protection tag on each data word in order to utilize memory more flexibly, although desirable, has not been economically feasible.
A second type of memory protection utilizes a tag to distinguish various memory categories. For example, a one bit tag might differentiate raw data from machine instructions, precluding data manipulation operations from being wrongly applied to program code. Also, tags might be employed to distinguish "capabilities" or memory access rights from other varieties of memory words (See, Hardward Support For Memory Protection: Capability Implementations, M. V. Wilkes, Proceedings Symposium on Architectural Support For Programming Languages and Operation Systems, March 1982, Association for Computing Machinery, No. 556811, pp. 107-116) These categories of protection also entail the full expense attendant to the storage of extra bits. A "semi-tagged" alternative has been proposed (See, M. V. Wilkes, supra), but is of limited applicability, and engenders the loss of one information bit in tagged items.
Accordingly, there is a need for an apparatus which provides the benefits of tagging on a word-by-word basis without imposing the significant additional cost of storing extra bits.